package LeetCode热题HOT100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class p216组合总和III {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k>n) {
            return res;
        }

        backTrack(k,n,1,0);
        return res;
    }

    List<Integer> arr=new ArrayList<>();
    private void backTrack(int k, int targetSum, int index,int sum) {
        //确定递归终止条件
        if (arr.size()==k) {
            if (sum==targetSum) {
                res.add(new ArrayList<>(arr));
                return;
            }
        }

        if (sum>targetSum) {
            //剪枝优化
            return;
        }

        //确定单层递归逻辑
        for (int i = index; i <=9 ; i++) {
            arr.add(i);
            backTrack(k,targetSum,i+1,sum+i);
            arr.remove(arr.size()-1);
        }
    }


    public static void main(String[] args) {
        List<Integer> arr=new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        arr.add(1);
        arr.add(1);
        arr.add(2);
        res.add(new ArrayList<>(arr));
        arr.clear();
        arr.add(5);
        res.add(new ArrayList<>(arr));
        System.out.println(res);
    }
}
